package Exercise;


import offer.binarytree.BinaryTree;

import java.util.ArrayList;
import java.util.Stack;

/**
 * Description：
 * Author: zhangc
 * Date：2017/8/3 14:45
 */
public class BinaryTreeSum {

    public static ArrayList<ArrayList<Integer>> FindPath(BinaryTree<Integer> root, int target) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        if (root == null)
            return list;
        Stack<BinaryTree<Integer>> stack = new Stack<>();
        findPath(root, list, stack, 0, target);
        return list;
    }


    private static void findPath(BinaryTree<Integer> head, ArrayList<ArrayList<Integer>> list, Stack<BinaryTree<Integer>> stack, int currentSum, int desSum) {
        if (head == null)
            return;
        stack.push(head);
        currentSum += head.value;
        if (head.left == null && head.right == null) {
            if (currentSum == desSum) {
                ArrayList<Integer> ints = new ArrayList<>();
                for (BinaryTree<Integer> tree : stack) {
                    ints.add(tree.value);
                }
            }
        }

        findPath(head.left, list, stack, currentSum, desSum);
        findPath(head.right, list, stack, currentSum, desSum);

        stack.pop();
    }

}
